/*
 * Task 1. Prime numbers.
 */
import java.util.Scanner;

/**
 * Program for search prime numbers.
 * Link http://en.wikipedia.org/wiki/Sieve_of_Atkin
 * @version 3.1 29 Jan 2013
 * @author Yegor Apolonov
 */
public class PrimeNumbers {
   
    final static int FIRST_PRIME_NUMBER = 2;
    final static int SECOND_PRIME_NUMBER = 3;
    final static int STEP_TO_ODD_NUMBER = 2;
    /**
     * Method finds all prime numbers
     * of range from 0 to N and
     * @return array with markers.
     * Source on web - www.itlab.unn.ru/file.php?id=643
     * @param upperLimit
     */
    private static boolean[] findPrimeNumbers(int upperLimit){

        boolean[] primeNumberFlags = new boolean[upperLimit];

        primeNumberFlags = initializeSieve(primeNumberFlags);

        primeNumberFlags = determineFlagsOfPrimes(primeNumberFlags);

        cleanFlagsOfSquareNumbers(primeNumberFlags);

        return primeNumberFlags;

    }

    private static boolean[] initializeSieve(boolean[] earlySieve) {
        for(int number = 0; number < earlySieve.length; number++) {
            earlySieve[number] = false;
        }
        /*Set flags for the first known prime numbers*/
        earlySieve[FIRST_PRIME_NUMBER] = true;
        earlySieve[SECOND_PRIME_NUMBER] = true;
        return earlySieve;
    }

    private static boolean[] determineFlagsOfPrimes(boolean[] sourceFlags) {

        int middleLimit = (int)Math.sqrt(sourceFlags.length);

        for(int firstNumber = 0; firstNumber <= middleLimit; firstNumber++) {
            int firstSquareSummand = firstNumber * firstNumber;

            for(int secondNumber = 0; secondNumber <= middleLimit; secondNumber++) {
                int secondSquareSummand = secondNumber * secondNumber;
                /*Three IQF is three irreducible quadratic forms (IQF)*/
                int[] IQF = createIQF(firstSquareSummand, secondSquareSummand);  
                modifyFlagsOfPrimes(IQF, sourceFlags);
            }
        }

     return sourceFlags;
    }

    
    private static int[] createIQF(int firstSummand, int secondSummand) {
        int[] IQF = new int[3];
        IQF[0] = 4 * firstSummand + secondSummand;
        IQF[1] = IQF[0] - firstSummand;
        IQF[2] = 0;

        if(firstSummand > secondSummand) {
           IQF[2] = 3 * firstSummand - secondSummand;
        }
        return IQF;
     }

    /**
     * Method checks feature primes according to the algorithm of Atkin.
     * www.itlab.unn.ru/file.php?id=643, page 11.
     * @param is 3 IQF and array sieve.
     */
    private static void modifyFlagsOfPrimes(int[] squareForms, boolean[] flagsOfanalyzedNumbers) {
        if((squareForms[0] % 12 == 1) || (squareForms[0] % 12 == 5)) {
            invertFlagsOfMultipleNumbers(squareForms[0], flagsOfanalyzedNumbers);
        }
        if(squareForms[1] % 12 == 7) {
            invertFlagsOfMultipleNumbers(squareForms[1], flagsOfanalyzedNumbers);
        }
        if(squareForms[2] % 12 == 11) {
            invertFlagsOfMultipleNumbers(squareForms[2], flagsOfanalyzedNumbers);
        }
    }

    private static void invertFlagsOfMultipleNumbers(int number, boolean[] flagsOfDetectedNumbers) {
        if(number <= flagsOfDetectedNumbers.length) {
           flagsOfDetectedNumbers[number] = !flagsOfDetectedNumbers[number];
        }
    }

    private static void cleanFlagsOfSquareNumbers(boolean[] flaggedSieve) {
 
        int boundary = flaggedSieve.length;
        int middleBoundary = (int)Math.sqrt(boundary);
        
        for(int localCounter = SECOND_PRIME_NUMBER; localCounter < boundary; localCounter += STEP_TO_ODD_NUMBER) {
            int positionStep = localCounter * localCounter;
            
            if((flaggedSieve[localCounter]) && (localCounter <= middleBoundary)) {
              
                for(int numberPosition = positionStep; numberPosition < boundary; numberPosition += positionStep) {
                    flaggedSieve[numberPosition] = false;
                    System.out.println(numberPosition + " is false");
                }
            }
        }
    }

    private static int inputLimitFromConsole() {
        System.out.println("Please, input max range of numbers N:");
        return new Scanner(System.in).nextInt();
    }
 
    /**
     * Method for printing prime numbers on display
     * @param primeNumbers is array after all operations
     * with flags in cells
     */
    private static void printNumbersFromFlags(boolean[] flagsOfNumbers) {
        for(int stepPoint = SECOND_PRIME_NUMBER; stepPoint < flagsOfNumbers.length; stepPoint += STEP_TO_ODD_NUMBER) {
            if(flagsOfNumbers[stepPoint]) {
               System.out.println(stepPoint);
            }
        }
    }

    public static void main(String[] args) {
        int limit = inputLimitFromConsole();
        boolean[] primeNumbers = findPrimeNumbers(limit);
        printNumbersFromFlags(primeNumbers);
    }

}
